This invention is concerned with improvements in arrays of machines such as data processing machines, and more particularly with improved networks for transfer of data between machines. Although the invention will be described with reference to an array of stand-alone computers, it will become apparent that the principles of the invention may be applied to arrays of unit devices other than computers in which there is a need for efficient communication or data transfer between the unit devices. Such unit devices will be termed "machines."
The computing rate of a serial computer is limited by the necessity for all operations to be performed in a serial fashion. It has long been recognized that faster execution of a large class of significant programs can be achieved by parallel processing, that is, execution of various parts of a program at the same time.
Parallel processing can take many forms, but one of the most powerful approaches is to use stand-alone serial machines interconnected in some fashion not only to allow each machine to work on some segment of the problem, but also to enable the various machines to communicate required intermediate results.
The central problem of such a system is the method of intercommunications which is provided. The serial machines can work on their program segments well enough, but it is essential that intercommunications be as efficient as possible. When large numbers of machines must communicate between any two computational segments, the "internal bandwidth" requirement can become very large. This situation develops in any program which attempts to model neural networks, for example, and there are many other examples.
Three basic approaches have been used historically to solve the interconnection problems. The first is a technique which is functionally similar to the operation of the telephone system: one user calls another, a link is established between the two users, and the information is transmitted. Examples of this system are Digital Equipment Corporation's UNIBUS system, and the well-known cross-bar switch. A serious disadvantage of the use of the UNIBUS for interconnecting serial computers is that the process is inherently serial, and all pairs of machines must be enumerated. The cross-bar switch on the other hand requires an amount of hardware which grows with the square of the number of devices to be interconnected, a fact which makes the cross-bar switch a prohibitive technique for even relatively small numbers of devices. Other "telephone system" schemes have similar drawbacks.
The second technique is the "central clearinghouse" approach. Here each machine first deposits a message in a central memory. Then a "master" processor picks up the messages and moves them to an area accessible to the particular receiving machines. To minimize complexity, only the master processor has access to the entire central memory. This process is also serial, since each message must pass through the bottleneck of the master processor. An example of this system exists in the ILLIAC computer. For even moderate internal bandwidth requirements, this system is slow.
The third technique can be likened to the post-office, where each serial machine becomes a postal sorting station and messages (letters) are routed through intermediate stations to destinations. Any system utilizing this scheme to communicate among component processors will be called a Post Office Transfer (POT)-array computer. Perhaps the best known POT-array computer is the ILLIAC IV, which uses the postal-sorting message system as its principal internal communications technique.
Historical practice has been to design POT-array computers by laying out the component serial machines on a two-dimensional array and connecting "nearest neighbor" machines by communications lines. Even this primitive configuration has a measure of the advantage which is potentially available in the POT-array intercommunications technique over the other known intercommunications methods already described. That advantage is that the process of intercommunications is no longer serial, but parallel. Thus the same computing power increase which is available through parallel computation during the execution portion becomes potentially available in the intercommunications portion of a program as well. Historical practice, however, has failed to recognize the full potential of the POT-array computer and to allow maximum parallel advantage to be achieved in the intercommunications portion of a program.